FIG. 1 depicts a conventional computer system 10. The computer system 10 has a processor 12, a main memory 14, a disk memory 16 and an input device 18, such as a keyboard and mouse. The devices 12-18 are connected to a bus 20 which transfers data, i.e., instructions and information, between each of these devices 12-18. A graphics controller 30 is also connected to the bus 20. As shown, the graphics controller 30 includes a drawing processor 31, a screen refresh controller 33 and a memory controller 32. The drawing processor 31 and screen refresh controller 33 output pixel addresses to the memory controller 32. The memory controller 32 is connected to the address inputs of a frame buffer 34. Illustratively, the frame buffer 34 comprises plural memory circuits 36-1, 36-2, 36-3 and 36-4. Illustratively, the memory circuits 36-1, 36-2, 36-3 and 36-4 are VRAMs or video random access, or DRAMs or dynamic random access memories such as the TMS44C251 manufactured by Texas lnstruments.TM.. Pixel data outputted from the frame buffer 34 is inputted to a digital to analog converter (DAC) 40 to produce an analog video signal. The analog video signal thus produced is displayed, e.g., in raster scan format, on the display device 42, e.g., a cathode ray tube (CRT) or liquid crystal display (LCD) monitor.
The display device 42 has a display screen with an array of pixels. The array can have a number of resolutions such as 1024.times.768, 1152.times.900, 1280.times.1024, 1600.times.1200, etc. In a refresh operation, the screen refresh controller 33 of the graphics controller 30 retrieves (reads-out) each pixel of a frame from the frame buffer 34 in row-column order. The retrieval of pixels is synchronized to the row-column raster scan of the display device 42 so that the appropriate luminance and chrominance signal is displayed on each pixel position of the display screen.
FIG. 2 illustrates the VRAMs 36-1 to 36-4 in greater detail. Each VRAM 36-1 to 36-4 includes a two-dimensional memory array 44 with plural storage locations for storing pixel data. The storage locations of the memory array 44 are organized into memory array rows and memory array columns. Each storage location is indexed by a memory address which includes a memory array row address component and a memory array column address component. For purposes of illustration, assume the VRAMs 36-1 to 36-4 each have a 256K*4 bit capacity, with 512 memory array rows and 512 memory array columns. As such, each address has 18 bits Address17:0! including a 9 bit memory array row address component Address17:9! and a 9 bit memory array column address component Address8:0!. When a particular memory location is to be accessed (i.e., data is to be written into, or to be read-out from, a particular memory location), the 18 bit address of the memory location is inputted to the VRAM 36-1, 36-2, 36-3 or 36-4. The respective row and column address components are inputted to a Y-decoder 46 and an X-decoder 48, respectively. Control signals are also generated including a row address strobe (RAS) signal and a column address strobe (CAS) signal which strobe, i.e., store, the row and column address components in the Y-decoder 46 and X-decoder 48. The data access (read or write) can then occur to the addressed memory location. Note that the RAS signal need not always be generated. In some memory circuits 36-1 to 36-4, if multiple memory locations are to be accessed on the same row of the memory array 44, only the CAS signal need be generated to change the column address component. In such memory circuits, multiple sequential accesses to the same row of the memory array take less time than sequential accesses to different rows. (In the case the frame buffer 34 is implemented with static random access memories or SRAMs, the RAS and CAS signals are replaced by a single chip enable signal CE.)
Typically, pixels must be displayed at a much higher rate than they can be retrieved (read out) from each individual VRAM 36-1 to 36-4. For instance, pixel data may have to be produced at the rate of one pixel data every 9 nsec. However, the delay in retrieving a single pixel from the VRAM 36-1 may be 35 nsec. To enable displaying pixels at such a high rate, the pixel data is typically interleaved over the VRAMs 36-1, 36-2, 36-3 and 36-4 as illustrated in FIG. 2. In FIG. 2, the sequence of pixels which form each row are alternately stored in the VRAMs 36-1 to 36-4 in a round robin fashion. For instance, consider the sequence of pixel data to be displayed on row 0 of the display screen of the display device 42. The pixel data stored in column 0 of row 0 of the display device may be stored at address 0 (row 0 column 0 of the memory array 44) in VRAM 36-1. The next pixel, to be displayed in column 1 of row 0 may be stored in address 0 (row 0 column 0 of the memory array 44) of VRAM 36-2. The pixel to be displayed in column 2 of row 0 may be stored in address 0 (row 0 column 0 of the memory array 44) of VRAM 36-3. The pixel to be displayed in column 3 of row 0 may be stored in address 0 (row 0 column 0 of memory array 44) of VRAM 36-4. The pixel to be displayed in column 4 of row 0 may be stored in address 1 (row 0 column 1 of memory array 44) of VRAM 36-1 and so on.
When pixel data is read-out during a screen refresh operation, the screen refresh controller 33 (FIG. 1) outputs the pixel addresses of the pixels at the display rate (e.g., 9 nsec) of the display device 42 (FIG. 1). The memory controller 32 translates the pixel addresses to memory addresses and alternately outputs each memory address to the VRAMs 36-1 to 36-4 in a round robin fashion. That is, the first address is outputted to VRAM 36-1, the second address to VRAM 36-2, the third address to VRAM 36-3, the fourth address to VRAM 36-4, the fifth address to VRAM 36-1, etc. Note that the VRAM 36-1 has not completed reading out the first pixel data at the time the second VRAM 36-2 receives the address of the second pixel data. In fact, in this example, the VRAM 36-1 does not complete reading out the first pixel data until all of the VRAMs 36-2, 36-3 and 36-4 receive the addresses of the second, third and fourth pixel data. Thus, the read operations occur simultaneously in each VRAM 36-1 to 36-4 to produce the pixel data at the display rate of the display device 42.
Herein, the terms "the number of banks over which interleaving is performed," and "N-way interleaving" should be distinguished. The number of banks over which interleaving is performed is the total number of memory banks which receive interleaved data. N-way interleaving means that data is assigned, in a round robin fashion, to N memory banks. That is, each round, data is stored in only N of the number of memory banks over which interleaving is performed. In the above example, the number of banks over which interleaving is performed is 4 and 4-way interleaving is performed. As described below, in N-way interleaving, N need not equal the number of banks over which interleaving is performed.
Interleaving poses a problem for memory architecture design. Specifically, most interleaving techniques divide the available memory circuits into equal size banks. Particular bits of the memory address for data are used as bank selector bits. For instance, in FIG. 2, the addresses for the data may be 20 bits long, even though only 18 bits are needed to address each memory storage location of each VRAM memory array. The two least significant bits of the address of each data word may be used as a memory bank selector. Thus, if the two least significant bits are `00`, VRAM 36-1 is selected for storing the data. If the two least significant bits are `01`, VRAM 36-2 is selected., etc. The problem with this technique is that the number of memory banks must be a power of 2, i.e., 2 banks, 4 banks, 8 banks, etc. Memory circuits only come in fixed sizes such as 256K, 1M, 4M, etc. Consider a frame buffer which stores pixel data for a 1024.times.768 resolution display as 4 bytes of data. Such a frame buffer could be implemented with 3 VRAMs of 1 Mbyte each. However, in order to provide for interleaving, at least four banks of 1 Mbyte each must be provided. In short, more memory capacity than is needed must be provided to allow for interleaving.
Interleaving has also been considered in connection with the shared memory 14. However, the problems to be solved are slightly different. Consider that most computer systems 10 are provided with a shared memory 14 formed from a number of DRAMs. Typically, the DRAMs are organized into banks. The computer system 10 is usually sold with a certain amount of DRAMs occupying some, but not all, of the memory bank slots. (Usually, DRAM ICs are soldered onto small printed circuit cards called single in-line memory modules or SIMMs, which SIMMs are inserted into respective memory bank slots.) As such, additional vacant bank slots are available for adding more DRAMs to increase the total storage capacity. The shared memory 14 is designed to accommodate different permutations of numbers of memory circuits and storage capacities. The prior art has suggested using interleaving to decrease the access time of the shared memory 14, in general, although no specific minimal access time need be obtained.
U.S. Pat. No. 5,269,010 teaches a memory controller for generating RAS and CAS signals for plural memory banks. Each memory bank has two memory circuits which receive the same RAS and CAS signals. Each memory bank can have a different storage capacity. The memory controller also accommodates interleaving although no specific interleaving scheme is disclosed.
U.S. Pat. No. 5,301,292 discloses a circuit for 2-way, 4-way or no interleaving over memory banks. The disclosed circuit is specifically designed for memory architectures in which the memory capacity of each bank need not be the same. However, when the banks are the same, the memory controller circuit can accommodate 2 or 4 way interleaving of data words and blocks over a power of 2 number of banks. No specific interleaving examples are disclosed.
U.S. Pat. No. 5,051,889 teaches to interleave pages (e.g., 2 Kbyte blocks of data words) into different memory banks. The page size is selected to be the same as the amount of data that can be stored in a full row of the memory array of a bank. This enables retrieving a whole page without having to generate a RAS signal. In this patent, the number N, for N-way interleaving, equals the number of banks over which interleaving is performed.
U.S. Pat. No. 5,341,486 teaches a memory interleaving technique for accommodating a number of memory banks which is different than a power of 2, e.g., seven memory banks. The memory banks are divided into multiple subsets of powers of two. For instance, seven memory banks are divided into a subset of four banks, a subset of two banks and a subset of one bank. The address space of the data words is divided into appropriate contiguous segments which match the capacity of each subset. For instance, the data word address space is divided into 4/7, 2/7 and 1/7 contiguous segments. The data words with addresses in the 4/7 segment are 4-way interleaved over the first subset of four banks. The data words with addresses in the 2/7 segment are 2-way interleaved over the second subset of two banks. Finally, the data words with addresses in the 1/7 segment are stored in the last subset of one bank. In any event, the number N, for N-way interleaving, equals the number of banks in the respective subset over which interleaving is performed.
U.S. Pat. No. 5,293,607 teaches a memory architecture which can accommodate a number of memory banks other than a power of 2, e.g., seven memory banks. Data words are interleaved amongst a "moving" subset of four of the memory banks at one time. That is, data words are sequentially interleaved over banks 1-4, then over banks 2-5, then over banks 3-6, then over banks 4,5,6 and 1, etc. The data are furthermore stored at non-sequential addresses while being interleaved. For example, consider the storage of pixel data for row 0, columns 0,1,2,3,4,5, . . . of the display screen, in an interleaved fashion over banks 1-4. The pixel data for row 0, column 0 is stored at memory address 0 of bank 1. The pixel data for row 0, column 1 is stored at memory address 1 of bank 2. The pixel data for row 0, column 2 is stored at memory address 2 of bank 3. The pixel data for row 0, column 3 is stored at memory address 3 of bank 4. The pixel data for row 0, column 4 is stored at memory address 4 of bank 1. The pixel data for row 0, column 5 is stored at memory address 5 of bank 2, and so on. Therefore, 4-way interleaving is performed over 7 memory banks. In this case, the number N, for N-way interleaving, does not equal the number of banks over which interleaving is performed.
Consider now that the same frame buffer 34 (FIG. 1) may be used to display pixels on display monitors 42 (FIG. 1) with different resolutions. In any event, the row and column dimensions of the memory array 44 (FIG. 1) typically do not match the row and column dimensions of the display screen. One manner of storing the data in the frame buffer 34 (FIG. 1) is to associate each row of pixel data on the display screen with a corresponding row in the VRAMs. Thus, pixel data on row 0 of the display screen is only stored on row 0 of the VRAMs 36-1 to 36-4, pixel data on row 1 of the display screen is only stored on row 1 of the VRAMs 36-1 to 36-4, etc. In order to store pixel data in this fashion, the VRAMs 36-1 to 36-4 must have memory arrays which are sufficiently wide to store a whole display screen row of pixel data. For example, in the case that the display is 1152.times.900, and the interleaving is over four VRAMs 36-1 to 36-4, then VRAMs may be provided having memory arrays with at least 288 columns each. The problem is that the dimensions of VRAM memory arrays are integral powers of 2. Thus, the closest matching VRAM is one with 512 columns. As such, no data is stored in the latter 224 columns of each VRAM row. This is shown in FIG. 3. Likewise, additional VRAMs 36-5, 36-6, 36-7 and 36-8 are needed to accommodate all 900 rows of pixel data that can be displayed on the display screen. In all, only about 50.2% of the storage capacity of the frame buffer 34 is utilized to store a frame of pixel data for display on the display screen.
Alternatively, the prior art has suggested a linear addressing strategy for storing pixel data such as is shown in FIG. 4. See U.S. Pat. Nos. 5,321,425, 5,268,682 and 5,268,681. A shown, the rows of the memory arrays are not strictly assigned to pixel data of corresponding rows of the display screen. Rather, the storage locations are assigned in strict sequential order to each pixel in order of increasing raster scan display order. As such, the pixel data of each row is stored sequentially and contiguously in each VRAM. For instance, consider the above example for a 1152.times.900 display screen using 256K*4 VRAMs. The pixel data of row 0, columns 0,4,8,12, . . . , 1148 are stored in row 0, columns 0,1,2,3, . . . , 287 of VRAM 36-1. The pixel data of row 1, columns 0,4,8,12, . . . , 896 are stored in row 0, columns 288, 289, 290, 291, . . . , 511 of VRAM 36-1. The remaining pixel data of row 1 of the display screen to be stored in VRAM 36-1, namely, the pixel data of columns 900, 904, 908, . . . , 1148, is stored on row 1 columns 0,1,2, . . . , 63 of the memory array 44 of the VRAM 36-1. Likewise, VRAM 36-2 stores pixel data of row 0, columns 1,5,9,13, . . . , 1149 in row 0, columns 0,1,2,3, . . . , 287, and pixel data of row 0, columns 0,5,9,13, . . . , 897 in row 0, columns 288, 289, 290, . . . , 511 of VRAM 36-2, and so on. The linear addressing scheme advantageously conserves storage capacity in the frame buffer 34.
Desirably, both interleaving and linear memory addressing are combined. U.S. Pat. No. 5,349,372 teaches a combined interleaving and linear addressing technique. According to this patent, pixel data is interleaved over three memory banks and linear addressing is used to organize the storage of pixel data in the memory banks. Each bank includes a single VRAM with 512 rows and 512 columns.
None of the prior art solutions is quite adequate for the general case of an arbitrary number of memory banks and varying interleaving. U.S. Pat. No. 5,269,010 teaches a flexible memory controller but does not teach any specific memory interleaving technique. U.S. Pat. No. 5,301,292 teaches a memory controller which can accommodate 2-way and 4-way interleaving of data words or pages (over a number of DRAM banks equal to a power of 2), but does not teach how to interleave over a number of memory banks which is not a power of 2. U.S. Pat. No. 5,051,889 teaches a circuit that interleaves pages over 2 memory banks so that RAS control signals can be avoided when multiple sequential accesses occur to the same page. Again, this patent does not teach how to interleave over a number of memory banks which is not a power of 2. U.S. Pat. No. 5,341,486 does teach how to interleave over a number of data banks which is not a power of 2 by dividing the memory banks into subsets of powers of 2. However, the number of banks over which interleaving occurs varies over each subset, i.e., 4-way interleaving is used over a subset of four banks while 2-way interleaving is used over a subset of two banks. This cannot be used in a VRAM if at least 4-way interleaving is necessary to retrieve pixel data at a precise rate. U.S. Pat. No. 5,293,607 teaches how to interleave data over a "moving" subset of four memory banks when the total number of memory banks is not a power of 2. However, the interleaving strategy is complicated requiring complex circuitry to determine both the correct bank and memory address in the bank. U.S. Pat. No. 5,349,372 teaches a frame buffer utilizing linear addressing and 3-way interleaving to interleave pixel data over three memory banks. However, the interleaving strategy is also complex since modulo three arithmetic is necessary to achieve the 3-way interleaving. Furthermore, no explanation is provided for interleaving over any other arbitrary number of banks (which number is not a power of two) or to provide a power of 2, i.e., 2.sup.n -way interleaving over the three banks.
It is therefore an object to overcome the disadvantages of the prior art. It is a particular object to provide a power of two, i.e., 2.sup.n,-way interleaving over a number of memory banks which is not a power of 2.